'''
https://leetcode.cn/problems/combinations/description/?envType=study-plan-v2&envId=top-interview-150
'''
from collections import deque
from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        path = deque()
        def dfs(rest, pre):
            if rest == 0:
                res.append(list(path))
                return
            for num in range(pre + 1, n+1):
                path.append(num)
                dfs(rest-1, num)
                path.pop()
        dfs(k, 0)
        return res